public class Solution1278 {
    public int palindromePartition(String s, int k) {
        int[][] f=new int[s.length()][k+1];
        for (int i=0;i<s.length();i++){
            f[i][1]=cal(s.substring(0,i+1));
            for (int j=2;j<=Math.min(k,i+1);j++){
                f[i][j]=Integer.MAX_VALUE;
                for (int t=j-2;t<i;t++){
                    f[i][j]=Math.min(f[i][j],f[t][j-1]+cal(s.substring(t+1,i+1)));
                }
            }
        }
        return f[s.length()-1][k];
    }

    private int cal(String s) {
        int ans=0;
        for (int l=0,r=s.length()-1;l<r;l++,r--){
            if (s.charAt(l)!=s.charAt(r)){
                ans++;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1278().palindromePartition("abab",3));
    }
}
